МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Курсова робота
з дисципліни: “ Паралельні та розподілені обчислення”
на тему:
«Паралельне виконання операцій множення матриць»
Завдання
Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=5Б , n2=3П, n3=2І – КІ-44
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Жолубак Іван Михайлович КІ-44:
Завдання відповідно варіанту задане в таблиці 1.
Таблиця 1 Завдання відповідно варіанту
Розміри матриць
К-сть
процесорів (Р)
Тип початкового
завантаження даних
Співвідношення часових параметрів
N1
N2
N3
190
213
73
8
Завантаження з спільної пам’яті
tU=10tS=4tP=2tZ=10tW
Отже маємо матрицю А(120*110) та матрицю В(110*120)
Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом:
3b-6b-2b-5b-10b-13b-14b-11b – КІ-44, де «nb»- номер букви П.І.Б студента.
Жолубак Іван Михайлович КІ-44:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Ж
О
Л
У
Б
А
К
І
В
А
Н
М
И
Х
А
Й
Л
О
В
И
Ч
3
1
4
2
5
8
6
7
Отримаємо – ЛАОБНИХМ
Для ЛАОБНИХМ отримаємо 212, 27, 250, 35, 134, 91, 127, 43. Даний набір чисел записуємо у стовпець і переводимо і двійкове 8-ми розрядне число. В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
212 - 11010100 01010100
027 - 00011011 00011011
250 - 11111010 11011010
035 - 00100011 00100011
134 - 10000110 10000110
091 - 01011011 01011011
127 - 01111111 01111101
043 - 00101011 00101010
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує певну 8-ми процесорну систему (структуру) із направленими зв’язками між вершинами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
КІ-41 … КІ-46: type=1(спільна пам’ять),type=2(через один процесор), type=3(розподілена пам’ять). 0809319
type=(0+8+0+9+3+1+9)=30 mod 3 + 1 = 1(з спільної пам’яті)
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k = 7-кількість цифр в номері залікової книжки.
tU=(9 +1)tS=(3 +1)tP=(1 +1)tZ=(9+1)tW
tU=10tW; tS=tw; tP=5/2tw; tZ=5tw;
Анотація
В даній курсовій роботі було розроблено програму для множення двох матриць розміром 190*216 та 216*73 на восьми процесорах, з заданою структурою зв’язків. Завантаження даних в процесори відбувається через спільну пам’ять. Збір даних відбувається на одному процесорі. Також було розроблено функціональну схему і визначено основні характеристики розробленого паралельного алгоритму.
Програма в даній курсовій роботі написана на мові С++ з використанням бібліотек MPI та має консольний інтерфейс.
Зміст
Вступ…………………………………………………………………………………..6
1. Теоретичний розділ 8
2. Проектування граф-схеми виконання алгоритму 12
3. Розробка функціональної схеми 18
4. Розрахунковий розділ 22
5. Розробка програми виконання заданої функції (алгоритму) 29
Висновок
Список використаної літератури
Додатки
Вступ
На сьогоднішній день найбільш перспективні дві основні технології, які мають баг...
